import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @ClassName Code05_FindKinKM
 * @Description: TODO
 * @Author: JCC
 * @CreateTime: 2023/12/11 20:28
 */
public class Code05_FindMayKInKM {

    // 数组中所有的数都出现了M次，只有一种数出现了K次(没出现K次则返回-1)
    public static int onlyKTimes(int[] array, int k, int m) {
        int[] solidArr = new int[32];
        for (int num : array) {
            for (int i = 0; i < 32; i++) {
                if (((num >> i) & 1) != 0) {
                    solidArr[i]++;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            if (solidArr[i] % m == 0) {
                continue;
            }
            if (solidArr[i] % m == k) {
                ans |= (1 << i);
            } else {
                return -1;
            }
        }
        if (ans == 0) {
            int count = 0;
            for (int num : array) {
                if (num == 0) {
                    count++;
                }
            }
            if (count != k) {
                return -1;
            }
        }
        return ans;
    }

    // 测试部分 只有一种数出现了K次(没出现K次则返回-1)
    public static int test(int[] array, int k, int m) {
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int num : array) {
            if (hashMap.containsKey(num)) {
                hashMap.put(num, hashMap.get(num) + 1);
            } else {
                hashMap.put(num, 1);
            }
        }
        for (int num : hashMap.keySet()) {
            if (hashMap.get(num) == k) {
                return num;
            }
        }
        return -1;
    }

    // 生成一个K次的数和其他m次的数的数组
    public static int[] randArray(int numKinds, int range, int k, int m) {
        HashSet<Integer> hashSet = new HashSet<>();
        int kNum = randNum(range);
        int kTimes = Math.random() < 0.5 ? k : (int) (Math.random() * (m - 1)) + 1;
        int[] array = new int[kTimes + (numKinds - 1) * m];
        int index = 0;
        for (; index < kTimes; index++) {
            array[index] = kNum;
        }
        numKinds--;
        hashSet.add(kNum);
        while (numKinds != 0) {
            int num = 0;
            do {
                num = randNum(range);
            } while (hashSet.contains(num));
            numKinds--;
            hashSet.add(num);
            for (int i = 0; i < m; i++) {
                array[index++] = num;
            }
        }
        shuffle(array);
        return array;
    }

    // 随机打乱数组
    public static void shuffle(int[] array) {
        int len = array.length;
        for (int i = len - 1; i > 0; i--) {
            int randIndex = (int) (Math.random() * i);
            // 用这种方式交换必须是两个引用的地址不一样的，否则就是0
            array[i] = array[i] ^ array[randIndex];
            array[randIndex] = array[i] ^ array[randIndex];
            array[i] = array[i] ^ array[randIndex];
        }

        // i == 0 这个为也发生了交换，而且是数组相同位置进行交换，会变成0
        // 所以这种方式是错误的
        /*for (int i = len - 1; i >= 0; i--) {
            int randIndex = (int) (Math.random() * i);
            // 用这种方式交换必须是两个引用的地址不一样的，否则就是0
            array[i] = array[i] ^ array[randIndex];
            array[randIndex] = array[i] ^ array[randIndex];
            array[i] = array[i] ^ array[randIndex];
        }*/
    }

    // 生成随机数[-range,range]
    public static int randNum(int range) {
        if (range % 2 == 1) {
            range--;
        }
        return (int) (Math.random() * (range * 2 + 1)) - range;
    }

    public static void main(String[] args) {
        int numKinds = 10;
        int range = 200;
        int max = 9;
        int testTimes = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < testTimes; i++) {
            int a = (int) (Math.random() * max) + 1;
            int b = (int) (Math.random() * max) + 1;
            int k = Math.min(a, b);
            int m = Math.max(a, b);
            /*if (k == m) {
                // k != 0
                // 这种方式会使 k == 0 这种情况发生
                k--;
            }*/
            if (k == m) {
                m++;
            }
            int[] array = randArray(numKinds, range, k, m);
            int onlyKTimes = onlyKTimes(array, k, m);
            int testNum = test(array, k, m);
            if (onlyKTimes != testNum) {
                System.out.println("测试异常");
                System.out.println(Arrays.toString(array));
                System.out.println("k = " + k);
                System.out.println("m = " + m);
                System.out.println("onlyKTimes = " + onlyKTimes);
                System.out.println("testNum = " + testNum);
                return;
            }
        }
        System.out.println("测试结束");
    }
}
